//
//  ProblemOffer53.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/7.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 53 - I. 在排序数组中查找数字 I
 统计一个数字在排序数组中出现的次数。

 示例 1:
     输入: nums = [5,7,7,8,8,10], target = 8
     输出: 2
 示例 2:
     输入: nums = [5,7,7,8,8,10], target = 6
     输出: 0
 限制：
    0 <= 数组长度 <= 50000
 */
@objcMembers class ProblemOffer53: NSObject {
    func solution() {
        print(searchDi([5,7,7,8,8,10], 8))
        print(searchDi([5,7,7,8,8,10], 6))
        print(searchDi([1], 1))
        print(searchDi([], 1))
        print(searchDi([1, 2], 1))
        print(searchDi([1, 1, 2], 1))
        print(searchDi([1, 1, 1], 1))
        print(searchDi([1, 1, 2], 2))
        print(searchDi([1, 2, 2, 2, 3], 2))
        print(searchDi([2,2], 3))
        print(searchDi([2,2], 1))
        print(searchDi([2,2], 2))
    }
    
    /*
     二分法
     找到target，然后左右遍历统计个数
     */
    func search(_ nums: [Int], _ target: Int) -> Int {
        var l = 0
        var r = nums.count - 1
        var mid = 0
        var targetIndex = -1
        while l <= r {
            mid = l + (r - l) >> 1
            if nums[mid] == target {
                targetIndex = mid
                break
            } else if nums[mid] > target {
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        
        if targetIndex == -1 {
            return 0
        }
        l = targetIndex - 1
        r = targetIndex + 1
        mid = 1
        while (l >= 0 && nums[l] == target)  || (r < nums.count && nums[r] == target) {
            if (l >= 0 && nums[l] == target) {
                mid += 1
                l -= 1
            }
            if (r < nums.count && nums[r] == target) {
                mid += 1
                r += 1
            }
        }
        return mid
    }
    
    // 二分法：
    // 寻找target左边界和target-1的左边界
    func searchDi(_ nums: [Int], _ target: Int) -> Int {
        if nums.count == 0 {
            return 0
        }
        let right = searchTargetRight(nums, nums.count-1, target)
        let left = searchTargetRight(nums, right >= nums.count ? nums.count-1 : right, target-1)

        return right - left
    }
    
    func searchTargetRight(_ nums: [Int], _ end: Int, _ target: Int) -> Int {
        var i = 0
        var j = end
        var m = 0

        while i <= j {
            m = (i + j) >> 1
            if nums[m] <= target {
                i = m + 1
            } else {
                j = m - 1
            }
        }
        return i
    }
}
